The present invention relates to digital image scaling.
Digital image processing of images by a computer is a relatively recent development. In its short history, it has been applied to a variety of technical fields with varying degrees of success. The coordinate conversion of a two-dimensional digital data is known as xe2x80x9cre-samplingxe2x80x9d. In order to re-sample the digital input data, data processing techniques such as nearest neighbor interpolation, bilinear interpolation, and interpolation using the cubic convolution method are known.
Image scaling techniques may be differentiated according to the interpolation method used to compute a new value at each scaled location. Of particular interest are those techniques which operate in the spatial domain and employ local, polynomial interpolants. Of these, there are two primary approaches, namely, regional (two-dimensional) interpolants and profile-curve (one-dimensional) interpolants. In either case, the derived polynomial provides image values only for points in the interior to a given 2xc3x972 pixel neighborhood (the domain) of the interpolation. Accordingly, to scale an entire image requires computing individual interpolants for each such neighborhood.
The nearest neighbor interpolation technique is the simplest interpolation scheme, wherein the data of the output pixel (picture element) is taken to be that of the input pixel nearest to the position to which it maps. This interpolation technique, however, introduces a sawtooth effect at the edges of the obtained image. On the other hand, bilinear interpolation obtains the output pixel by interpolating adjacent four-pixel neighborhoods, but still does not provide sufficient contour smoothing. This problem is particularly notable if the geometric operation involves magnification.
Region interpolant techniques typically involve either directly computing an interpolating surface or computing a set of weights based on an underlying set of 2D polynomial equations. In the case of interpolating a surface, the value at an interpolated position is obtained by directly evaluating the surface polynomial at that point. In the case of computing a set of weights, they determine the proportionate contributions of neighboring pixel values to the interpolated value. Techniques involving surface computations can be computationally intensive to compute and evaluate, and increasing in computational complexity as the degree of the polynomial increases. Furthermore, for degree dxe2x89xa72, such surfaces may involve over-determined systems. For example, this occurs when a polynomial of degree d is fit to a (d+1)xc3x97(d+1) pixel neighborhood. Referring to FIG. 1, a bicubic surface is fit a representative 4xc3x974 neighborhood. A detail of the surface section corresponding to the central 2xc3x972 neighborhood is shown in FIG. 2 together with exemplary pixel values. The pixel values for the 4xc3x974 neighborhood of FIG. 1 are shown at the bottom, with the central 2xc3x972 neighborhood outlined. The central 2xc3x972 neighborhood outlined in FIG. 1 and shown in FIG. 2 is the only region used to interpolate image values that are to be used for the 2xc3x972 region.
The principal benefit of a surface interpolant is that, once computed, it can provide values for any point interior to its 2xc3x972 region by simply evaluating the surface at that point. In other words, there is no need to compute a new interpolant for other points within the region. However, as previously noted, it is computationally expensive to compute a surface interpolant. In addition, the system may be over-determined resulting in polynomials that do not exactly interpolate the boundary points of their central 2xc3x972 pixel neighborhood. More significantly, the exact boundary interpolation results in interpolants computed for adjacent neighborhoods that do not agree in their common boundary points. Not only do the boundary values for the computed points not agree with one another, they do not even agree with the underlying image points. In other words, the use of the surface interpolant may result in discontinuities at the region boundaries.
To illustrate this effect, FIG. 3 shows the comparison of the surface of FIG. 2 with another surface computed for an adjacent 2xc3x972 neighborhood. For convenience, each surface is displayed in its local coordinate system. However, it may be observed that their common points disagree in value. In particular, the values of 133.91, 120.24 vary significantly from the values of 136.715, 125.385, which should be identical.
One proposed improvement is to use an exactly determined (d+1)2xc3x97(d+1)2 system comprised of the four 2xc3x972 boundary pixels, their 1st derivatives, and their cross derivatives. Unfortunately, such a proposal is computationally expensive and inappropriate for a real time system with limited computational capability, such as a digital photocopier.
Referring to FIG. 4, the other principal approach of profile-curve interpolants uses profile curves fitting curves of degree d to corresponding d+1 contiguous pixels along d+1 adjacent rows (or columns). A transverse curve is then fit to corresponding points on the original curves, i.e., points with the identical row (or column) offset. An interpolated value is obtained by evaluating the transverse curve at the proper row (or column) offset. Profile-curve interpolants has the benefit of determining the value of any point along the ab line (aligned with C5) by evaluating transverse curve C5 at the proper offsets. On the other hand, to compute the values of other points in the neighborhood (e.g., c or d) entails fitting a new transverse curve with the appropriate offset along base curves (C1, C2, C3, C4) and evaluating that new curve at the corresponding point position. Moreover, to evaluate any point in region R2 involves a number of additional steps: fitting a new base curve to the four pixels to the right of curve C4; fitting a new transverse curve to the base curves at the appropriate offset; and evaluating the new transverse curve at the corresponding point position. Finally, to evaluate any point in region R3 involves fitting four new base curves now centered on R3; fitting a new transverse curve; and evaluating the transverse curve at the appropriate position. Unfortunately, the profile-curve interpolants are not well suited to transformations that are not axis-aligned (e.g., rotation, shearing, or warping), since the interpolation along the base curves will rarely produce actual output values.
The present invention overcomes the aforementioned drawbacks of the prior art by providing a system for modifying an image consisting of a plurality of pixels from a first scale to a second scale. The system determines an integer matrix that is independent of the values of the plurality of pixels of the image. The system also determines a first vector for a region of the first scale representative of a surface based on the coordinates of the first scale. Also, the system interpolates pixel locations in the second scale by scaling the coordinates of points of the first scale and computing a scaled second vector. A third vector is determined based, at least in part, upon the product of the first vector and the second vector, where the third vector has uneven scaling of its terms. A plurality of the terms of the third vector based upon a fractional scaling factor related to said uneven scaling and summing the components of the third vector.
The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention, taken in conjunction with the accompanying drawings.